In typical database systems, users store, update, and retrieve information by interacting with user applications (“clients”). The clients respond to the user's interaction by submitting commands to a database application responsible for maintaining the database (a “database server”). The database server responds to the commands by performing the specified operations on the database. To be correctly processed, the commands must comply with the database language that is supported by the database server. Such commands may come in a variety of forms known within the art, including structured query language (SQL) and data definition language (DDL) statements and blocks.
A database system may receive a query on the data managed by a database system. A query optimizer associated with the database system may generate one or more different candidate execution plans for the query, which are evaluated by the query optimizer to determine which execution plan should be used to compute the query.
A query execution plan defines steps for computing a query. An execution plan may be represented by a directed graph of interlinked nodes, referred to herein as operators, that each corresponds to a step or function of the execution plan, referred to herein as an execution plan operation. The hierarchy of the graph (i.e., directed tree) represents the order in which the execution plan operations are performed and how data flows between each of the execution plan operations. An execution plan operator may generate a set of rows as output. There are execution plan operators for performing operations such a table scan, an index scan, sort-merge join, nested-loop join, etc. One type of execution plan operator calls an index routine, defined through an extensible indexing mechanism as described in more detail below, to scan an index.
Query execution plans may be stored in cursor data structures, which allow the execution plans to be quickly executed and to be reused by the database system. For example, a database system may need to perform a particular query one or more times after creating an execution plan for the query. To execute the query, the database system may locate a cursor that the database system created for the execution plan of the query and execute the execution plan using the cursor, instead of compiling a new query execution plan.
When a query includes a reference to a particular resource, herein referred to as a resource path, the resource path may be included in the query execution plan for the query. Traditionally, the resource path is resolved, upon execution of the query execution plan, to determine the appropriate set of resources to which the resource path refers. Thus, a resource path may be resolved each time the database executes a particular query execution plan stored at a particular cursor. Resolving a resource path is computationally expensive because resolving the path requires the database system to perform a lookup to determine the set of resources to which the resource path refers.
Furthermore, various access methods may be used to retrieve data from a database for commands issued to the database system. Many access methods use indices to increase the speed of the data retrieval process. Typical database management systems have built-in support for a few standard types of access methods, such as access methods that use B+ Trees and Hash Tables, that may be used when the key values belong to standard sets of data types, such as numbers, strings, etc. The access methods that are built-in to a database system are referred to herein as native access methods.
A database system may also include a mechanism through which customized indices may be defined, i.e., an extensible indexing mechanism. Indices defined through an extensible indexing mechanism, referred to herein as extensible indexes, may be used to support complex data types that are not easily accessed through native access methods. Thus, extensible indexes may be defined to access complex data types such as text, spatial, image, video, audio, and hierarchically-organized data.
Index routines, also called index functions, are defined for each extensible index to allow the database system to interact with the extensible indices. A database system may assume that all non-native index types will support a certain set of such index routines. For example, one or more index definition methods, index maintenance methods, and index scan methods, etc., may be defined for each extensible index. These routines perform the same functions and may have a similar interface as the built-in routines called by the database server for native access methods. Because the database server knows the names and parameters of the routines that will manage index objects of the non-native index types, the database server can invoke the appropriate index routines in response to commands received from a client.
Index routines of an extensible indexing mechanism may also be defined to support operators that may be used in conjunction with a particular extensible index type, referred to herein as extensible operators. Such operators take advantage of the extensible index to perform operations on the data to which the extensible index corresponds.
Non-limiting examples of index routines, and the definition and use thereof, are given in Oracle® Database Data Cartridge Developer's Guide, 10g Release 2 (10.2) Part Number B14289-02, Chapters 8 and 9, accessed on Jul. 13, 2009, at “docs/cd/B19306—01/appdev.102/b14289/dcidmnidx.htm” found at the server download.oracle.com, the contents of which are incorporated by reference in their entirety for all purposes as if fully set forth herein.
Such index routines may be defined by clients of a database system using a procedural language, such as PLSQL or C. In contrast, queries on a database system are generally written in a language configured for data access, such as SQL. Thus, it is generally necessary to evaluate a query that includes an index routine using separate evaluation mechanisms for (a) the procedural language of the index routine, and (b) the language in which the rest of the query is defined.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.